package reviewAlgorithms.tree;

public class IsBalanced {
    int LeftDepth = 0;
    int rightDepth = 0;

    public static void main(String[] args) {

    }
    public static boolean isBalanced1(TreeNode root) {
        if (root == null){
            return true;
        }
        if (!isBalanced(root.left) || !isBalanced(root.right)){
            return false;
        }
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) < 2;
    }
    public static int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int leftDepth = maxDepth(root.left) + 1;
        int rightDepth = maxDepth(root.right) + 1;
        return Math.max(leftDepth,rightDepth);
    }

    public static boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
//        if (!isBalanced(root.left) || !isBalanced(root.right)){
//            return false;
//        }
        Object[] res = getBalance(root);
        return (Boolean) res[0];
    }

    private static Object[] getBalance(TreeNode root) {
        Object[] res = new Object[2];
        if (root == null){
            res[0] = true;
            res[1] = 0;
            return res;
        }
        Object[] leftState = getBalance(root.left);
        Object[] rightState = getBalance(root.right);
        res[0] = (Boolean)leftState[0] && (Boolean)rightState[0];
        res[0] = (Boolean)res[0] && Math.abs((int)leftState[1] - (int)rightState[1]) <= 1;
        res[1] = Math.max((int)leftState[1],(int)rightState[1]) + 1;
        return res;
    }
}
